public class Solution430 {

    public static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;

        public Node() {
        }

        public Node(int val, Node prev, Node next, Node child) {
            this.val = val;
            this.prev = prev;
            this.next = next;
            this.child = child;
        }
    }

    public Node flatten(Node head) {
        if (head==null) return null;
        Node node=head;
        search(node);
        return head;
    }

    public Node search(Node head){
        while (head.next!=null) {
            if (head.child != null) {
                Node node=search(head.child);
                node.next=head.next;
                head.next.prev=node;
                head.child.prev=head;
                head.next=head.child;
                head.child=null;
            }
            head=head.next;
        }
        if (head.child!=null){
            Node node=search(head.child);
            node.next=null;
            head.child.prev=head;
            head.next=head.child;
            head.child=null;
            head=node;
        }
        return head;
    }

    public static void main(String[] args) {
        Node node3=new Node(3,null,null,null);
        Node node2=new Node(2,null,null,null);
        Node node1=new Node(1,null,node2,node3);
        Node newNode=new Solution430().flatten(node1);
        while (newNode!=null){
            System.out.println(newNode.val);
            newNode=newNode.next;
        }
    }
}
